Голотипная таксономия
Процедура позволяет разбивать множество объектов на заданное количество кластеров.
Назначение
Решение задач районирования
Условия применимости
- Свойства могут быть арифметическими, логическими 1-го и 2-го рода, то есть, алгоритм может работать с разношкальными свойствами.
- Поскольку алгоритм рассматривает "выбросы" (ураганные значения) как отдельные компоненты, то для получения содержательного разбиения рекомендуется задавать Минимальный размер кластера. В этом случае компоненты, число объектов в которых будет мало (меньше порядка малости), будут отнесены к нулевой компоненте. Таким образом, в результирующем разбиении будет заказанное число больших компонент, а общее число компонент будет больше заказанного.
- Не при всех значениях параметров расчет будет завершен успешно. Необходимо, чтобы произведение параметров Минимальный размер кластера и Количество кластеров не превышало количества объектов, участвующих в расчете. Это условие является необходимым, но не является достаточным. В случае если расчет не удался, рекомендуется уменьшать значения входных параметров.
Параметры
Параметр Количество кластеров указывает алгоритму, на сколько частей разделить множество объектов. Размер кластеров можно регулировать, задавая Минимальный размер кластера.
Рекомендуется задавать значение Количество кластеров большим, это позволяет разбить множество объектов на большое число кластеров, а в поле Максимальное число кластеров указать желаемое число кластеров. В этом случае будет создано много кластеров, далее они будут отсортированы по размеру и на выходе пользователь получит желаемое число больших кластеров.
Также необходимо указать Название свойства результата
Рис.1 Форма задания параметров для метода Голотипная таксономия
Результат расчета
Результатом расчета является новое свойство, содержащее номера компонент. Каждому объекту соответствует номер компоненты, в которую он попал. Нумерация компонент идет по убыванию количества объектов в компоненте. То есть, первая компонента - самая крупная.
О работе алгоритма
Принцип работы алгоритма следующий:
- 1. Для всех объектов строится минимальное остовное дерево (подграф с минимальной суммарной длиной ребер, включающий все вершины) полного графа, в котором вершинами являются объекты, а ребрами - мера сходства между ними. Для этого используется модифицированный алгоритм Прима.
- 2. В полученном графе определяются K-1 ребер максимальной длины (где K-количество классов для разбиения). Эти ребра удаляются из графа.
- 3. В результате предыдущей операции граф разобьется на К связных компонент. Эти компоненты и будут результирующими классами.
- 4. Кластеры нумеруются в соответствии с их размером. Чем меньше номер кластера тем больше в него входит объектов.
Компоненты как и во всех голотипных алгоритмах строятся так, чтобы любые два объекта из компоненты были связаны цепочкой близко расположенных друг у другу объектов из той же компоненты. Таким образом, все множество объектов разбивается на "колбасы". При большом количестве объектов скорость работы процедуры может быть очень низкой. Длительность расчета увеличивается квадратично с ростом количеством объектов.